package cn.zyl.demo.java.sort;

import java.util.Arrays;

/**
 * BucketSort 类说明: 桶排序
 * <p>桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。</p>
 * <p>为了使桶排序更加高效，我们需要做到这两点：</p>
 * <p>在额外空间充足的情况下，尽量增大桶的数量</p>
 * <p>使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中</p>
 * <p>对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要</p>
 * @author wsz
 * @version v1.0
 * @date 2020-08-13
 */
public class BucketSort extends AbstractArraySortSimple{
    /**
     * 排序接口
     * <pre>
     *     最快:当输入的数据可以均匀的分配到每一个桶中
     *     最慢:当输入的数据被分配到了同一个桶中
     * </pre>
     * @param sourceArray 待排序数组
     * @param order       排序方式，(默认)升序 true；降序 false
     * @return 排序后的数组
     * @throws Exception 异常信息
     */
    @Override
    @SuppressWarnings({ "IntegerDivisionInFloatingPointContext"})
    public Integer[] sort(Integer[] sourceArray, Boolean order) throws Exception {
        int len = sourceArray.length;
        if(len <= N_0){return sourceArray;}
        Integer[] arr = copyArray(sourceArray,len);
        start();
        //桶数量
        int bucketSize = 11;
        //最小值，最大值
        int minVal = arr[N_0],maxVal = arr[N_0];
        for (Integer val:arr) {
            addOne();
            if(val < minVal){
                minVal = val;
            }else if(val > maxVal){
                maxVal = val;
            }
        }
        // 利用映射函数将数据分配到各个桶中
        int bucketCount = (int)Math.floor((maxVal-minVal)/bucketSize)+1,index;
        Integer[][] buckets = new Integer[bucketCount][0];
        for (int i = N_0; i < len; i++) {
            index = (int)Math.floor((arr[i]-minVal)/bucketSize);
            buckets[index] = append(buckets[index],arr[i]);
        }
        index = order ? N_0 : len-1;
        for(Integer[] bucket:buckets){
            if(bucket.length <= N_0){continue;}
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort(bucket);
            for(int val :bucket){
                if(order){
                    addOne();
                    arr[index++] = val;
                }else {
                    addOne();
                    arr[index--] = val;
                }
            }
        }
        end();
        return arr;
    }
    private Integer[] append(Integer[] arr,int val){
        addOne();
        arr = Arrays.copyOf(arr, arr.length+N_1);
        arr[arr.length - N_1] = val;
        return  arr;
    }
    private Integer[] insertSort(Integer[] sourceArray) throws Exception {
        Integer[] arr = Arrays.copyOf(sourceArray,sourceArray.length);
        int tmp,index;
        for (int i = N_0,len = arr.length; i < len; i++) {
            tmp = arr[i];
            index = i;
            while (index > N_0 && tmp < arr[index - N_1]){ arr[index] = arr[index - N_1];index --; }
            if(index != i){ arr[index] = tmp; addOne();}
        }
        return arr;
    }
    public static void main(String[] args) {
        int len = 15,max=100;
        //待排序数组初始化
        Integer[] arr = randomArray(len,max);
        AbstractArraySortSimple sort = new BucketSort();
        try {
            System.out.println("升序操作");
            printArray(sort.sort(arr, true));
            System.out.println("降序降序");
            printArray(sort.sort(arr, false));
        }catch (Exception e){
            e.printStackTrace();
        }
    }
}
